package com.caochenlei.graph;

import java.util.Stack;

public class DepthFirstPaths {
    private boolean[] marked;                   //索引代表顶点，值表示当前顶点是否已经被搜索
    private int[] edgeTo;                       //索引代表顶点，值代表从起点s到当前顶点路径上的最后一个顶点
    private int s;                              //记录有多少个顶点与顶点s相通

    public DepthFirstPaths(Graph G, int s) {    //构造深度优先搜索对象
        this.marked = new boolean[G.size()];    //初始化marked数组
        this.edgeTo = new int[G.size()];        //初始化edgeTo数组
        this.s = s;                             //初始化起点
        dfs(G, s);                              //使用深度优先搜索找出G图中起点为s的所有路径
    }

    private void dfs(Graph G, int v) {          //使用深度优先搜索找出G图中起点为s的所有路径
        marked[v] = true;                       //把v顶点标识为已搜索
        for (Integer w : G.adj(v)) {
            if (!marked[w]) {                   //判断当前w顶点有没有被搜索过
                edgeTo[w] = v;                  //到达顶点w的路径上的最后一个顶点是v
                dfs(G, w);                      //如果没有被搜索过，则递归调用dfs方法进行深度搜索
            }
        }
    }

    //判断v顶点与顶点s是否存在路径
    public boolean hasPathTo(int v) {
        return marked[v];
    }

    //找出从起点s到顶点v的路径
    public Stack<Integer> pathTo(int v) {
        if (!hasPathTo(v)) {
            return null;
        }
        Stack<Integer> path = new Stack<>();
        for (int x = v; x != s; x = edgeTo[x]) {
            path.push(x);
        }
        path.push(s);
        return path;
    }
}
